public class Sort {
    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    /**
     * 插入排序
     * @param array
     */
    public static void insertSort(int[] array){
        int len = array.length;
        for (int i = 1; i < len; i++) {
            int mid = array[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                if(array[j] > mid){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = mid;
        }
    }

    /**
     * 希尔排序
     * @param array
     */
    public static void shellSort(int[] array){
        int len = array.length;
        int gap = len/2;
        while(gap >= 1){
            shell(array,gap);
            gap /= 2;
        }
    }
    public static void shell(int[] array,int gap){
        int len = array.length;
        for (int i = gap; i < len; i++ ) {
            int mid = array[i];
            int j = i - gap;
            for (; j >= 0 ; j -= gap) {
                if(array[j] > mid){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = mid;
        }
    }

    /**
     * 选择排序
     * @param array
     */
    public static void selectSort(int[] array){
        int len = array.length;
        for(int i = 0;i < len;i++){
            int indexMin = i;
            for(int j = i + 1;j < len ;j++){
                if(array[j] < array[indexMin]){
                    indexMin = j;
                }
            }
            int tmp = array[i];
            array[i] = array[indexMin];
            array[indexMin] = tmp;
        }
    }

    /**
     * 堆排序
     * @param array
     */
    public static void createBigHeap(int[] array){
        int len = array.length;
        for (int i = (len - 1)/2; i >= 0 ; i--) {
            shiftDown(array,i);
        }
    }
    public static void shiftDown(int[] arr,int parent){
        int child = parent*2 + 1;
        while(child < arr.length){
            int tmp;
            if(child + 1 < arr.length && arr[child] < arr[child + 1]){
                tmp = child + 1;
            }else{
                tmp = child;
            }
            if(arr[tmp] > arr[parent]){
                int mid = arr[parent];
                arr[parent] = arr[tmp];
                arr[tmp] = mid;
            }else{
                break;
            }
            parent = tmp;
            child = parent * 2;
        }
    }

    /**
     * 冒泡排序
     * @param array
     */
    public static void bulluSort(int[] array){
        int len = array.length;
        for (int i = 0; i < len; i++) {
            boolean flag = true;
            for (int j = 0; j < len - 1 -i; j++) {
                if(array[j] > array[j + 1]){
                    swap(array,j,j+1);
                    flag = false;
                }
            }
            if(flag){
                return;
            }
        }
    }

    /**
     * 快速排序
     * @param array
     */
    public static void quickSort(int[] array){
        int len = array.length;
        quick(array,0,len - 1);
    }
    public static void quick(int[] array,int start,int end){
        int left = start;
        int right = end;
        if(right <= left){
            return;
        }
        int p = partition(array,start,end);
        quick(array,start,p - 1);
        quick(array,p + 1,end);
    }
    public static int partition(int[] arr,int left,int right){
        int key = arr[left];
        int i = left;
        while(left < right){

            while(left < right && arr[right] >= key){
                right--;
            }
            while(left < right && arr[left] <= key){
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,i,left);
        return left;
    }

    /**
     * 归并排序
     * @param array
     */
    public static void mergeSort(int[] array){
        mergeSortfunc(array,0,array.length);
    }
    public static void mergeSortfunc(int[] array,int left,int right){

    }

    /**
     * 独自写希尔排序
     * @param array
     * @return
     */
    public int[] myShellSort(int[] array) {
        //希尔排序
        int len = array.length;
        int gap = len / 2;
        while(gap >= 1){
            shell(array,gap);
            gap/=2;
        }
        return array;
    }

    /**
     * 利用选择排序交换
     */
    public static void myShell(int[] array,int gap){
        int len = array.length;
        for(int i = gap;i < len;i++){
            for(int j = i;j >= 0;j -= gap){
                if(j - gap >= 0 && array[j] < array[j - gap]){
                    swap(array,j,j - gap);
                }
            }
        }
    }
    /**
     利用插入排序交换
     */
    public static void myShell1(int[] array,int gap){
        int len = array.length;
        for(int i = gap;i < len;i++){
            int mid = array[i];
            for(int j = i - gap;j >= 0;j -= gap){
                if(mid < array[j]){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
                array[j] = mid;
            }
        }
    }
    /**
     * 再次练习堆排序
     */
    public int[] stackSort(int[] nums) {
        //堆排序
        int len = nums.length;
        createStack(nums);
        for(int i = len - 1;i >= 0;i--){
            swap(nums,0,i);
            shiftDown(nums,0,i - 1);
        }
        return nums;
    }
    public static void createStack(int[] nums){
        int len = nums.length;
        for(int i = (len - 1)/2;i >= 0;i--){
            shiftDown(nums,i,len - 1);
        }
    }
    public static void shiftDown(int[] nums ,int stack,int end){
        int i = stack;
        while(2*i + 1 <= end){
            int j = 2*i + 1;
            if(j + 1 <= end && nums[j] < nums[j + 1]){
                j++;
            }
            if(nums[j] > nums[i]){
                swap(nums,j,i);
            }else{
                break;
            }
            i = j;
        }
    }
//     //用于测试的main方法
//    public static void main(String[] args) {
//        int[] arr = {5, 3, 4, 6, 2};
//        quickSort(arr);
//        for (int num : arr) {
//            System.out.print(num + " ");
//        }
//    }
}
